<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link href="CSS/main.css" rel="stylesheet" type="text/css" />
<link href="CSS/style3.css" rel="stylesheet" type="text/css" />
<link href="CSS/Layer.css" rel="stylesheet" type="text/css" />
<title>LPA* - hoangvp 2010</title>
</head>

<body>
<script type="text/javascript" src="JS/priority_queue.js"></script>
<script type="text/javascript" src="JS/MathHelpers.js"></script>
<script type="text/javascript" src="JS/AJAX.js"></script>
<script type="text/javascript" src="JS/DOM.js"></script>
<script type="text/javascript" src="JS/layer.js"></script>
<?php
require_once 'Map.class.php';

$x = new Map("map.txt");
$x->printMap();
$x->generateJSCode2();
generateJSDebugCode($DEBUG_);
?>

<script type="text/javascript">
//heuristicFunction = diagonalAndEuclid;
heuristicFunction = manhattan;

function isBetter(a, b){
	return isBetterKey(a.key, b.key);
}

/*
 * Hàm calculateKey(s)
	k2 = min{g[s], rhs[s])
	k1 = k2 + h(s, s-goal)
	return {k1, k2}
 */
function calculateKey(s){
	 var k2 = min(s.cost, s.rhs);
	 var k1 = k2 + s.heuristic;
	 return new QueueKey(k1, k2);
 }

function changeKey(s){
	var newKey = calculateKey(s);
	s.key.k1 = newKey.k1;
	s.key.k2 = newKey.k2;
}
 
 function isBetterKey(key1, key2){
	 if(key1.k1 < key2.k1){
		 return BETTER;
	 } else if(key1.k1 == key2.k1 && key1.k2 < key2.k2){
		 return BETTER;
	 } else {
		 return WORSE;
	 }
 }

 function getKey(k){
	 return "("+k.key.k1+", "+k.key.k2+") ";
 }

function init(){					
	queue = new PriorityQueue({cmpFunc : isBetter});
	queue.displayOne = displayOneElementInQueue;
	traceMap = new Array();
	for(var i=0; i<m; ++i){				
		traceMap[i] = new Array(n);	
	}
	initHValue(globalFinish.x, globalFinish.y);	
	queue.push(globalStart);
	globalStart.rhs = 0;
	changeKey(globalStart);	

	setRHS(globalStart.x, globalStart.y, INFINITY);
	setG(globalStart.x, globalStart.y, INFINITY);
	setF(globalStart.x, globalStart.y, globalStart.key.k1);		
}

function setMinPred(u) {
	u.rhs = INFINITY;
	for(var i=startIndex; i<aroundLength; ++i) {
		var x = u.x + around[i][0];
		var y = u.y + around[i][1];
		if(doesPathExist(x, y, u.x, u.y)){
			var s = map[x][y];
			var costIfMoveFromS = getExactNumDigits(s.cost + costToMove(x, y, u.x, u.y), 2);
			if(u.rhs > costIfMoveFromS) {
				u.rhs = costIfMoveFromS;
				traceMap[u.x][u.y] = s;
			}
		}
	}	
}

function setPosition(u) {
	if(u.status == IN_OPEN_SET){
		if(u.cost == u.rhs){
			queue.remove(u);
			u.status = IN_CLOSED_SET;
		} else {
			changeKey(u);
		}
	} else if(u.cost != u.rhs){
		changeKey(u);
		queue.push(u);
		u.status = IN_OPEN_SET;
	}	
}

function updateVertex(u) {
	setMinPred(u);
	setPosition(u);	
}

function computeShortestPath(){		
	var startTime = new Date();
	var found  = false;			
	loopsCount = 0;
	expandCount = 0;
	while(!queue.isEmpty()){
		if(isBetterKey(queue.top().key, calculateKey(globalFinish))==WORSE && globalFinish.rhs == globalFinish.cost){
			break;
		}
		++loopsCount;
		var u = queue.top();
		logDebug("TopKey = "+getKey(u)+" KeyGoal = " + getKey(globalFinish));		
		setTimeout('fillRed('+u.x+', '+u.y+');', SPEED*loopsCount);
		logDebug("("+u.x + ", "+u.y+"): g="+u.cost+", rhs="+u.rhs+", h="+heuristicFunction(u, globalFinish)+", k="+getKey(u));
		if(u.cost > u.rhs) {
			u.cost = u.rhs;
			queue.pop();
			u.status = IN_CLOSED_SET;
			for(var i=startIndex; i<aroundLength; ++i) {
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(doesPathExist(u.x, u.y, x, y)) {
					logDebug("\tMở rộng tới ("+x+" "+y+")");
					var s = map[x][y];
					var costIfMoveFromU = getExactNumDigits(u.cost + costToMove(u.x, u.y, x, y), 2);					
					if(!isStart(s) && s.rhs > costIfMoveFromU) {
						s.rhs = costIfMoveFromU;
						traceMap[x][y] = u;
						setPosition(s);
						logDebug("\tĐặt ("+x+", "+y+") tới từ ("+u.x+", "+u.y+") với rhs = "+ s.rhs);
					}
					var statements ='fillYellow('+x+', '+y+');setG('+x+', '+y+', '+s.cost+');setRHS('+x+', '+y+', '+s.rhs+');setF('+x+', '+y+', '+s.key.k1+');';
					setTimeout(statements, SPEED*loopsCount + DELAY);
					++expandCount;
				}
			}
		} else {
			u.cost = INFINITY;
			setPosition(u);
			for(var i=startIndex; i<=aroundLength; ++i) {
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(doesPathExist(u.x, u.y, x, y)) {
					logDebug("\tMở rộng tới ("+x+" "+y+")");
					var s = map[x][y];										
					if(!isStart(s) && (traceMap[x][y] == u || s==u)) {
						updateVertex(s);
					}
					var statements ='fillYellow('+x+', '+y+');setG('+x+', '+y+', '+s.cost+');setRHS('+x+', '+y+', '+s.rhs+');setF('+x+', '+y+', '+s.key.k1+');';
					setTimeout(statements, SPEED*loopsCount + DELAY);
					++expandCount;
				}
			}
		}			
		setTimeout('setG('+u.x+', '+u.y+', '+u.cost+');setRHS('+u.x+', '+u.y+', '+u.rhs+');setF('+u.x+', '+u.y+', '+u.key.k1+');', SPEED*loopsCount);
		queue.adjust();

		/*
		logDebug("OPEN SET:");
		queue.display();
		*/
	}
	var finishTime = new Date();	

	if(globalFinish.cost == globalFinish.rhs && globalFinish.cost != INFINITY){
		found = true;
	}
	
	//Trace path
	if(found){
		//alert("Đã tìm thấy đường đi");
		tracePath(found, traceMap, loopsCount);
	}
	
	/*
	log("Trace map");
	var q = "";	
	for(var i=0; i<m; ++i){				
		for(var j=0; j<n; ++j){
			if(traceMap[i][j]){			
				log("(" + i + ", " + j + ") come from (" +traceMap[i][j].x + ", " + traceMap[i][j].y + ")");
			}
			q += "("+i+", "+j+", "+map[i][j].cost+", "+map[i][j].rhs+") ";
		}		
		q += "\n";
	}
	log(q);
	*/	
	statistic(++turn, globalFinish.cost, loopsCount, expandCount, finishTime.getTime() - startTime.getTime());
}

function displayOneElementInQueue(u){
	logDebug("\t("+u.x + ", "+u.y+"): g="+u.cost+", rhs="+u.rhs+", h="+u.heuristic+", k="+getKey(u));
}

var changedVerticesArray = new Array();
function updateChanging(){
	queue.clear();
	clearNavigation();
	while(changedVerticesArray.length > 0) {
		var t = changedVerticesArray.pop();
		terrain[t.x][t.y] = t.cost;
		var u = map[t.x][t.y];				
		updateVertex(u);
		var statements ='fillYellow('+u.x+', '+u.y+');setG('+u.x+', '+u.y+', '+u.cost+');setRHS('+u.x+', '+u.y+', '+u.rhs+');setF('+u.x+', '+u.y+', '+u.key.k1+');';
		eval(statements);
		if(u.cost == 0) {	//newCost < oldCost <=> turn to space						
			for(var i=startIndex; i<aroundLength; ++i) {
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(doesPathExist(u.x, u.y, x, y)) {
					var s = map[x][y];
					var costIfMoveFromU = getExactNumDigits(u.cost + costToMove(u.x, u.y, x, y), 2);
					if(s.rhs > costIfMoveFromU) {
						s.rhs = costIfMoveFromU;
						traceMap[x][y] = u;
						setPosition(s);
						changeKey(s);
						var statements ='fillYellow('+x+', '+y+');setG('+x+', '+y+', '+s.cost+');setRHS('+x+', '+y+', '+s.rhs+');setF('+x+', '+y+', '+s.key.k1+');';
						eval(statements);								
					}					
				}
			}
		} else {	//newCost > oldCost <=> turn to obstacle
			for(var i=startIndex; i<aroundLength; ++i) {
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(isInMap(x, y)) {					
					terrain[u.x][u.y] = 0;
					if(doesPathExist(u.x, u.y, x, y)) {
						terrain[u.x][u.y] = 1;
						var s = map[x][y];
						updateVertex(s);
						changeKey(s);
						var statements ='fillYellow('+x+', '+y+');setG('+x+', '+y+', '+s.cost+');setRHS('+x+', '+y+', '+s.rhs+');setF('+x+', '+y+', '+s.key.k1+');';
						eval(statements);										
					} else {
						terrain[u.x][u.y] = 1;
					}
				}
			}
		}
	}	
	queue.adjust();	

	/*
	logDebug("OPEN SET:" + queue.getSize());
	queue.display();
	*/
	
	//log("Done!");
}

function didVertexChange(u){
	var cvaLength = changedVerticesArray.length;
	for(var i=0; i<cvaLength; ++i){		
		if(nodesEqual(u, changedVerticesArray[i])){
			return i;
		}
	}
	return -1;
}
 
function search(){	
	var f = document.route;
	var fx = f.fromX.value;
	var fy = f.fromY.value;
	var tx = f.toX.value;
	var ty = f.toY.value;
	var startChange = (!isStart(map[fx][fy]) && map[fx][fy].status != IN_OPEN_SET && turn>0) ? true : false;
	var finishChange = (!isFinish(map[tx][ty]) && turn>0) ? true : false;		
	globalStart = map[fx][fy];
	globalFinish = map[tx][ty];
	if(turn == 0){
		init();
	}
	if(startChange){
		alert("Ô xuất phát đã thay đổi! LPA* không sử dụng được các thông tin có trước nên phải thực hiện lại từ đầu như A*\nKhông thực hiện yêu cầu tìm đường!");
		return;
	}
	if(finishChange){		
		heuristicWasInitialized = false;
	}
	if(!heuristicWasInitialized){
		initHValue(globalFinish.x, globalFinish.y);
	}
	
	computeShortestPath();	
}

function changeTerrain(a){
	if(a) {
		beginChangeTerrain();	
	} else {
		endChangeTerrain();
	}
}

function beginChangeTerrain(){
	changeCellFunc();
	document.searchFrm.searchBtn.disabled = "disabled";	
}

var onclickFuncs = [];
function changeCellFunc(){
	if(document.searchFrm.changeBtn.checked){
		//Change new onclick functions
		for(var i=0; i<m; ++i){
			onclickFuncs[i] = [];
			for(var j=0; j<n; ++j){
				var t = getMapCell(i, j);
				onclickFuncs[i][j] = t.getAttribute("onclick");
				t.setAttribute("onclick", "toogleCell("+i+", "+j+");");				
			}
		}
	} else {
		//Load original onclick functions
		for(var i=0; i<m; ++i){
			for(var j=0; j<n; ++j){
				getMapCell(i, j).setAttribute("onclick", onclickFuncs[i][j]);
			}
		}
		onclickFuncs.length = 0;
	}
}

function toogleCell(x, y){	
	var t = getMapCell(x, y);
	if(t.className == "wall"){
		t.className = "";
		terrain[x][y] = 0;
	} else {
		t.className = "wall";
		terrain[x][y] = 1;
	}
	var i = didVertexChange(map[x][y]);
	if(i > -1){
		changedVerticesArray.splice(i, 1);
	} else {
		changedVerticesArray.push(new NewCost(x, y, terrain[x][y]));
	}
}

function endChangeTerrain(){
	updateChanging();
	changeCellFunc();
	document.searchFrm.searchBtn.disabled = "";	

	var s = "";
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			s += terrain[i][j] + " ";
		}
		s += "\n";
	}
	s += "\n";
	logDebug(s);
}

function clearNavigation(){	
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			var t = getMapCell(i, j);
			switch (t.className){
				case "n":
				case "ne":
				case "nw":
				case "w":
				case "s":
				case "se":
				case "sw":
				case "e":
					t.className = "exm";
				default: break;
			}
			t.style.backgroundColor = "#FFF";
		}
	}
}
</script>
<form name="searchFrm">
	<input type="button" name="searchBtn" value="Bắt đầu" onclick="searchBtnOnclickFunc(this);" />
	<input type="button" name="resetBtn" value="Mới" onclick="window.location.reload();" /><br />
	<input type="checkbox" name="changeBtn" onclick="changeTerrain(this.checked);" /> Thay đổi bản đồ 
	<input type="button" name="saveBtn" value="Lưu bản đồ" onclick="save();" />
</form>
<div id="cost"></div>
<div>
<table id="statisticTable" border="1">
	<tr>
		<th>Lượt</th>		
		<th>Chi phí</th>
		<th>Số đỉnh được xét</th>
		<th>Số đỉnh được mở rộng</th>
		<th>Thời gian (miligiây)</th>
	</tr>
</table>
<textarea id="log" rows="30" cols="100"></textarea></div>
<script type="text/javascript">
document.searchFrm.searchBtn.disabled = "";
document.searchFrm.changeBtn.checked = false;
</script>
</body>
</html>
